/*
 * One example for NOI CSP-J Lesson 7:
 * <https://courses.fmsoft.cn/plzs/noijunior-graph-and-graph-theory.html>
 *
 * Author: Vincent Wei
 *  - <https://github.com/VincentWei>
 *  - <https://gitee.com/vincentwei7>
 *
 * Copyright (C) 2025 FMSoft <https://www.fmsoft.cn>.
 * License: GPLv3
 */
#include <iostream>           // for std::cout
#include <vector>             // for std::vector
#include <utility>            // for std::pair

using namespace std;

using adj_list = vector<vector<int>>;

using namespace std;

// 向无向图中添加边
void addEdge(adj_list &graph, int s, int t)
{
    graph[s].push_back(t);
    graph[t].push_back(s);
}

// 从指定顶点处递归执行 DFS 的函数
void dfs_from(adj_list &graph, vector<bool> &visited, int s, vector<int> &res)
{
    // 标记当前顶点已被访问
    visited[s] = true;

    res.push_back(s);

    // 递归访问所有尚未被访问的邻接顶点
    for (int i : graph[s]) {
        if (visited[i] == false)
            dfs_from(graph, visited, i, res);
    }
}

// 对整个图执行 DFS 的入口函数
vector<int> dfs(adj_list &graph)
{
    vector<bool> visited(graph.size(), false);
    vector<int> res;

    // 遍历所有的顶点已处理可能的断开图
    for (int i = 0; i < (int)graph.size(); i++) {
        if (visited[i] == false) {
            // 如果顶点 i 未被访问，则从该顶点执行 DFS
            dfs_from(graph, visited, i, res);
        }
    }

    return res;
}

int main()
{
    int V = 6;

    // 定义图的边
    vector<pair<int, int>> edges = {
        {1, 2}, {2, 0}, {0, 3}, {4, 5}
    };

    // 使用邻接表来定义这个图
    adj_list graph(V);

    // 将边添加到图中
    for (auto &e : edges)
        addEdge(graph, e.first, e.second);

    // 执行 DFS
    vector<int> res = dfs(graph);

    // 输出结果
    for (auto it : res)
        cout << it << " ";
    cout << endl;

    return 0;
}

